package edu.spbsu.nonsm00th.computgeom.chull.impl;

import edu.spbsu.nonsm00th.computgeom.chull.ConvexHull;
import edu.spbsu.nonsm00th.computgeom.util.D2Util;
import edu.spbsu.nonsm00th.computgeom.util.DNUtil;
import edu.spbsu.nonsm00th.model.Point;
import edu.spbsu.nonsm00th.model.enums.Orientation;
import edu.spbsu.nonsm00th.util.Precondition;
import java.util.ArrayList;
import java.util.List;

/**
 * Realization of Jarvis convex hull algorithm.
 * Should be used only for 2-dimensional point lists.
 *
 * @author mbuzdov
 */
public class D2JarvisConvexHull implements ConvexHull {

    public void convexHull(List<Point> list) {
        Precondition.argsNotNull(list);
        if (0 == list.size()) {
            return;
        }

        Point min = DNUtil.findCartesianMinimum(list);
        List<Point> result = new ArrayList<Point>();
        result.add(min);

        boolean flag = false;
        do {
            Point last = result.get(result.size() - 1);
            Point next = list.get(0);
            for (int i = 1; i < list.size(); i++) {
                Point candidate = list.get(i);
                if (!last.equals(candidate) && Orientation.ABOVE == D2Util.getOrientation(last, candidate, next)) {
                    next = candidate;
                }
            }

            if (min.equals(next)) {
                flag = true;
            } else {
                result.add(next);
                list.remove(next);
            }
        } while (!flag);

        list.clear();
        list.addAll(result);
    }

}
